<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        // shell sort

        const arr = [8, 9, 1, 7, 2, 3, 5, 4, 6, 0];

        function shellSort(arr) {
            const len = arr.length
            for (let gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
                for (let i = gap; i < len; i++) {
                    const current = arr[i]
                    let j = i
                    while (j - gap >= 0 && current < arr[j - gap]) {
                        arr[j] = arr[j - gap]
                        j = j - gap
                    }
                    arr[j] = current
                }
            }
            return arr
        }

        console.log('希尔排序', shellSort(arr))

        // 归并排序 https://gitee.com/shuwenjun/oss/raw/master/uPic/GuaUpH.jpg
        function merge(left, right) {
            let temp = []
            while (left.length > 0 && right.length > 0) {
                if (left[0] < right[0]) {
                    temp.push(left[0])
                    left.shift()
                } else {
                    temp.push(right[0])
                    right.shift
                }
            }
            return temp.concat(left, right)
        }

        function mergeSort(arr) {
            if (arr.length === 1) {
                return arr
            }
            const mid = Math.floor(arr.length / 2)
            const left = arr.slice(0, mid)
            const right = arr.slice(mid)
            return merge(mergeSort(left), mergeSort(right))
        }

        console.log('归并排序', mergeSort(arr))


        // 快速排序
        function quickSort(arr) {
            if (arr.length <= 1) {
                return arr
            }
            const pivotIndex = Math.floor(arr.length / 2)
            const pivot = arr.splice(pivotIndex, 1)
            let left = []
            let right = []
            for (let i in arr) {
                if (arr[i] < pivot) {
                    left.push(arr[i])
                } else {
                    right.push(arr[i])
                }
            }

            return quickSort(left).concat(pivot, quickSort(right))
        }

        console.log('快速排序--->>', quickSort(arr))
    </script>
</body>

</html>